package 力扣链表;

public class Leedcode82删除排序链表中的重复元素 {
    public static void main(String[] args) {
        ListNode node5 = new ListNode(3,null);
        ListNode node4 = new ListNode(3,node5);
        ListNode node3 = new ListNode(2,node4);
        ListNode node2 = new ListNode(1,node3);
        ListNode node1 = new ListNode(1,node2);
        ListNode node = deleteDuplicates(node1);
        while (node != null){
            System.out.println(node.val);
            node = node.next;
        }
    }
    //三指针法
    public static ListNode deleteDuplicates1(ListNode head) {
        //创建一个虚拟节点，防止头节点就是重复的节点，而导致头节点无法删除
        ListNode dummyHead = new ListNode();
        //创建一个prev节点用来遍历虚拟节点绑定的链表
        ListNode prev = dummyHead;
        //让虚拟节点的next指向链表的头节点
        dummyHead.next = head;
        //创建一个新的节点，用来指向虚拟节点的下一个节点
        ListNode cur = prev.next;
        //如果cur不为空，说明链表至少存在一个节点
        while (cur != null){
            //创建一个新的节点next，初识默认指向cur的next，next的作用是来用来判断cur和next是否为重复节点
            ListNode next = cur.next;
            //next=null，说明此时已经将整个链表遍历结束（链表只有一个元素），此时返回dummyHead.next;
            if (next == null){
                return dummyHead.next;
            }
            //走到这里说明此时链表的遍历没有到最后
            //如果cur和next节点的值相等，说明节点是重复的，此时所有需要删除节点，如果不相等，说明没有重复节点，三个指针同时向后移动，开始下一次while循环

            //如果不相等，执行if语句，说明此时节点不为重复节点
            if (cur.val != next.val){
                //将三个节点全部后移一位，这里只写prev后移和cur的后移，是应为next在进入while循环时，定义的就是cur的下一个节点，默认就相当于后移一位
                prev = prev.next;
                cur = cur.next;
            }else {
                //如果存在重复值，next一直后移，直到找到不重复的节点，找到next与cur不重复的节点以后，将prev.next = next;直接删除prev到next之间所有重复的节点
                //因为要执行next = next.next,所以在这里需要保证next不为空，否则会空指针异常
                while (next != null && cur.val == next.val){
                    next = next.next;
                }
                //走到这里说明此时next节点与cur不重复,让prev.next指向next，删除所有重复的节点，让cur=next，开始下一次循环时，cur = next ，next = cur.next；继续用来判断是否存在重复节点
                prev.next = next;
                cur = next;
            }
        }
        //走到这里说明此时已经遍历完成所有的节点，返回dummy.next；
        //因为dummyHead没有存储val，dummyhead.next指向head头节点，所以返回demmyHead.next;
        return dummyHead.next;
    }
    //递归解法

    /**
     * 方法语义：给你一个链表的头节点，你就可以删除链表中所有重复出现的所有节点
     * @param head
     * @return
     */
    //此方法不对，分析的思路不对
    public static ListNode deleteDuplicates2(ListNode head) {
        //1.终止条件
        //如果链表为空，或者链表中只有一个节点，肯定就不会存在重复节点
        if (head == null || head.next == null){
            return head;
        }
        //走到这里说明链表至少存在两个节点
        //需要创建一个虚拟节点用来删除头节点就是重复节点的情况
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;
        //将头节点以后的节点传入具有删除重复节点的方法中，会返回一个新的节点
        ListNode newHead = deleteDuplicates(head.next);
        //判断newHead和head的是否重复
        if (head.val == newHead.val){
            //执行到此，说明节点head和剩余节点删除重复节点以后返回的新节点相等，说明head和newHead重复。
            //此时将dummyHead.next = newHead.next就会将head和newHead重复的节点全部删掉
            dummyHead.next = newHead.next;
        }else {
            //走到这里，说明head和newHead不重复,直接拼接
            head.next = newHead;
        }
        //拼接完成，返回dummyHead.next
        return dummyHead.next;
    }

    /**
     * 方法语义：给你一个链表的头节点，你就可以删除链表中所有重复出现的所有节点,返回一个新节点
     * @param head
     * @return
     */
    public static ListNode deleteDuplicates(ListNode head) {
        //终止条件
        if (head == null || head.next == null){
            return head;
        }
        //说明至少存在两个节点
        //判断两节点是否相等，如果不相等
        if (head.val != head.next.val){
            //如果不相等 ,  当前头节点直接拼接剩余节点删除重复节点的后返回的新节点头
            head.next = deleteDuplicates(head.next);
            return head;
        }else {
            //两节点重复
            ListNode node = head.next;
            while (node != null && node.val == head.val){
                node = node.next;
            }
            //如果重复，找到重复的节点以后，调用改方法，直接不和头节点拼接，直接返回，就会将重复的头节点一并删除掉
            return deleteDuplicates(node);
        }
    }
}
